Codeforces Round#606 Div.2 A~E题解

A：
大意：
一个“美丽的数”的定义是，每一位数都是相同的（例如33，44，9999）。给定一个n，求1~n有多少个这样“美丽的数”。
思路：
我们发现一个美丽的数的条件是非常苛刻的，同时一个数要是美丽的一定是1/11/111/...的倍数，因此我们可以按这样的连续的1为基数进行枚举，看求出来的数是否在n的范围内，在则累加答案，否则说明后面再怎么做也得不到更多的答案了（基数按递增顺序枚举），即可退出。
代码：
B:
大意：
给你n个正数的序列a，每次可以从中选择一个偶数C，使序列中所有C/=2，问经过几次这样的操作可以使整个序列全部变成奇数。
思路：
首先我们可以想到贪心地选择最大的数开始操作一定不会变差，因此我们可以想到从大到小地来执行操作。其次，题目中所给的操作是对序列中所有的数进行操作的，因此我们需要有一种结构动态的维护序列中某一个特定的值的个数，于是这里使用map存储值-个数，既满足了值从大到小枚举，又能动态地维护个数，剩下的记一个数就可以了。
代码：https://codeforces.com/contest/1277/submission/66966463
C：
大意：
给你一个非空的长度为n的字符串，删去其中的一些字符（可以不删）使得序列中没有任何一个子串是“one”或"two"，求最少的删除次数，以及删去的位置（也就是方案）。
思路：
首先删去这件事很像是一个基础的dp问题，但是这里题目要求我们输出方案具体如何删除的，因此就不能单纯的只是dp找最小值。这里可以思考一个问题：删去一个字符会有怎样的影响？
对于子串中的"one"或者"two"，很显然每次出现两者其一就需要一次删去来才能使字符串中没有这两者，但是有一个情况例外，就是"twone"这个形式，只需要一次操作而不是两次，因此我们可以利用string对象自带的find函数来搜索twone,one,two分别出现的次数，并记录删去位置的方案。其次，如果要删去一个位置上的字符使的这两种形式不再出现，我们可以想到只要删去中间位置上的字符，就可以彻底的删除掉这两种形式，因为如果删去开头或是结尾的字符可能导致前后有字符会接上重新出现特定形式（比如"twoo"删去o就会导致后面的o接上又出现two，但是删去中间位置的t就一定不会再出现）。
分析到这里，总体的策略就是：
①利用find函数找到字符串S中是否有特定形式的字符
②删去中间位置的字符
代码：https://codeforces.com/contest/1277/submission/72781805
D:
大意：
给定n个不同的"binary words"（只由0和1组成的字符串），现要玩一个游戏，排列n个字符串，且满足任意一对字符串之间是第i个字符串的末尾字母和第i+1个字符串的起始字母是不同的，给定你一种操作可以取反整个字符串，求可以使得整个排列满足所需的最小操作次数。
思路：待写
代码：https://codeforces.com/contest/1277/submission/67006358
E：
大意：
给定一个n个点m条边的无向图和两个特殊点a,b。找出满足这样条件：①u < v②u != a&u!=b&v!=a&v!=b且从u走到v的路径上一定经过a和b的二元组(u,v)的个数。
思路：
这个题的关键问题就在于怎样的两个点的路径，相连之后是一定要经过a和b的。我们不妨反过来思考：从a或b出发的路径可以到达哪些点？我们把a和b两个点扯出来看一下：

我们可以把从a出发的所有的点标记成红色的，从b出发的所有的点标记成绿色的。那么在红色和绿色的范围内去掉直接和a和b相连的点，在左边和右边分别a和b两侧的点是不是就是满足题意中所说的，从u到v且一定是路径上需要经过a和b这两个点的二元组，由此做法就明确了：
①从a和b两个点分别跑dfs，标记所有能到达的点
②从已经标记了的点中挖掉两者都可以到达的点以及a和b本身，剩下的就是两侧的点
③答案就是两侧的点的数量乘积（注意范围）
代码：https://codeforces.com/contest/1277/submission/72778293
F：
待写